package org.cos.generation.util.agorithm;

import java.util.Stack;

import org.cos.generation.epda.State;
import org.cos.generation.epda.State.Transition;

public class Tarjan {
	
	private int[] sccRoot;
	
	private Stack<Integer> sccStack;
	
	private int order;
	
	private int[] nodeOrder;
	
	private int[] nodeLowlink;
	
	private State[] states;
	
	public Tarjan(){
		
	}
	
	public int[] tarjan(State[] states) {
		this.states = states; 
		int size = states.length;
		
		nodeOrder = new int[size];
		nodeLowlink = new int[size];
		
		sccRoot = new int[size];
		sccStack = new Stack<Integer>();

		order = 1;
		for (int i = 0; i < size; i++) {
			if (nodeOrder[i] == 0) {
				nullDfs(i);
			}
		}

		return sccRoot;
	}
	
	private void nullDfs(int index) {
		nodeOrder[index] = order;
		nodeLowlink[index] = order;
		order++;
		sccStack.push(index);
		for (Transition trans : states[index].getTransitions()) {
			if (trans.getMethod() == null) {
				Integer tail = trans.getTailIndex();
				if (nodeOrder[tail] == 0) {
					nullDfs(tail);
					if (nodeLowlink[tail] < nodeLowlink[index]) {
						nodeLowlink[index] = nodeLowlink[tail];
					}
				} else if (sccStack.contains(tail)) {
					if (nodeOrder[tail] < nodeLowlink[index]) {
						nodeLowlink[index] = nodeOrder[tail];
					}
				}
			}
		}
		if (nodeOrder[index] == nodeLowlink[index]) {
			Integer u;
			do {
				u = sccStack.pop();
				sccRoot[u] = index;
			} while (u != index);
		}
	}
	
}
